Day 3 - Functional 資料結構 (1)

functional 資料結構 (functional data structure) 就是只使用 pure function 來做事的資料結構，如同 Day 2 - 什麼是 Funcational Programming? 中有提到的，pure function 不能修改某處的資料結構或變數值，以及其它有 side effect 的事情，換句話說就是 不可變 (immutable) 的資料結構，

舉例來說，數字 3 或數字 4 皆是不可變，當我們處理 3 + 4 這種表達式的時候，我們直接得到結果 7 ，而不是修改 3 或 4 的值，

那這是不是代表所有的計算、操作都要複製值才能做呢？那可未必，我們先來看一個基礎的資料結構，Linked List：

enum List[+A]:
  /** 表示為一個空的 List */
  case Nil
  /** Cons 為 constructor 的縮寫，表示為非空的 List，請注意 `tail` 為另一個 List[A]，有可能是 `Nil` 或 `Cons` */
  case Cons(head: A, tail: List[A])

object List: // `List` 的 companion object，定義許多 List 的相關作業
  def sum(ints: List[Int]): Int = ints match // 使用 pattern match 來加總 List 中的元素
    case Nil => 0 // 若欲加總的是空 list 則給它 0
    case Cons(x,xs) => x + sum(xs) // 把目前的 `x` 加上其他剩下值的加總

  def product(doubles: List[Double]): Double = doubles match
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)

  def apply[A](as: A*): List[A] = // 可變參數語法
    if as.isEmpty then Nil
    else Cons(as.head, apply(as.tail*))

這是一個簡單的單向 Linked List 定義。

Scala 3 的 Enum 預設會建立 sealed class，而 sealed 關鍵字是用來限制我們只有在 相同的檔案中 才能定義、擴展其子類，在 Scala 2 時我們得用 sealed trait List[A] 來明確使用 sealed 闗鍵字；

apply function 是 Scala 的語法蜜糖，當我們用 List(1, 2, 3) 時，會被編譯成 List.apply(1, 2, 3)；

而 Scala 的可變參數 (Variadic function syntax) 是用來讓 function 能有彈性的接受多個參數；

而 List 的多型 A 型態前有 + 這個符號，代表了 variance annotation，有點難解釋自己去看 文件 吧！

Pattern Match

pattern match 對我們使用 Scala 撰寫 Functional Programming 中佔有相當重要的一席之地，請務必搞懂它。

而我們在 companion object 中，我們有 2 個 function 是使用 Scala 的 pattern match 來實現，pattern match 是一種用 pattern (模式) 來檢查值的機制，一個成功的 match (配對) 也能讓該值被解構成它原來的組成樣子，就當它是吃了 buff 的 java switch 吧，順道一提 case 語句中也能加入 if/else 判斷；

讓我們來看一下 pattern match 的例子：

List(1, 2, 3) = Cons(1, Cons(2, Cons(3, Nil)))

• List(1, 2, 3) match { case _ => 42 } 其結果為 42，_ 代表了萬用配對。

• List(1, 2, 3) match { case Cons(h, _) => h } 其結果為 1，我們使用建構模式來確認 List 是不是用 Cons(head, tail) 的方式來建構，然後我們將 head 的值補捉成變數 h，最後其回傳。

• List(1,2,3) match { case Cons(_, t) => t } 其結果為 List(2,3)。

• List(1,2,3) match { case Nil => 42 } 因未配對成功，會拋出 MatchError。

我們也能配對比較複雜的結構，

• List(1,2,3) match { case Cons(1, Cons(2, Cons(v, _))) => v } 其結果為 3，因為前面的結構皆符合。

pattern match 會由上而下的依序配對，那麼最後來用個 Exercise 來了解是不是真的懂得 pattern match 吧！

Exercise 1

result 的值為何？

  val result = List(1,2,3,4,5) match
    case Cons(x, Cons(2, Cons(4, _))) => x
    case Nil => 42
    case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
    case Cons(h, t) => h + sum(t)
    case _ => 101

今天比較像 Scala 教學，明天我們繼續。

Day 3 - Exercise answer